The present invention relates to the efficient and reliable transmission of packet or cell-based information, such as frame relay, SS#7, ISDN, Internet or asynchronous transfer mode (ATM) based information, via wireless links. More specifically, the present invention relates to a method and apparatus for fast acquisition and synchronization of frames for transmission over satellite and wireless links without the use of any overhead pattern bits for acquisition or synchronization. While the present invention is applicable all of the foregoing and other similar types of cell or packet-based transmission formats, the ATM format will be the exemplary focus of one preferred embodiment for purposes of providing an enabling disclosure, written description and best mode for the present invention.
There are a variety of methods for transmitting information via a broadband Integrated Services Digital Network (B-ISDN), using a variety of protocols related to Asynchronous Transport Mode (ATM), frame relay mode, Internet, ISDN and SS#7 modes of transmission. The ATM mode, as the exemplary preferred embodiment, is a method for transmitting information via a broadband Integrated Services Digital Network (B-ISDN). A group called the International Telephone and Telegraph Consultative Committee (CCITT) originally investigated this mode. The group, currently called the International Telecommunication Unionxe2x80x94Telecommunications Standards Sector (ITU-TSS), investigated a new form of ISDN that would have the flexibility to accommodate a large number of channels and the ability to transfer large amounts of data at a very fast rate. At the end of the study, the committee decided to adopt ATM as the target transfer mode for the B-ISDN. The ITU-TSS is currently defining the wide area network (WAN) standards for ATM.
ATM is a transfer mode that sends 53 octet-sized packets of information across a network from one communication device to another. The 53 octets are assembled as a xe2x80x9ccellxe2x80x9d, which comprises 48 octets of data information, referred to as the xe2x80x9cpayloadxe2x80x9d, and 5 octets of xe2x80x9cheaderxe2x80x9d information (including the routing information). The header and data information must be organized into cells so that when the cells are filled, they can be sent when an open slot of 53 octets becomes available.
Within a system that transmits ATM cells or packets, the end-to-end connection along which the user sends data is conventionally identified as a virtual channel connection (VCC). The VCC is unidirectional but VCCs occur in pairs, thus making the connection bidirectional. Each virtual channel is within a virtual path (VP), meaning a group of virtual channels that are associated so as to be sent in the same direction. Each VC and VP have specially signed numbers called virtual channel identifiers (VCI) and virtual path identifiers (VPI), respectively. These numbers help the system determine the direction in which the cell should be sent or where the cell belongs.
There are two forms of headers that are specified in the CCITT Recommendation I.361. Each form is 5 octets long. There also are two different ATM network connections, each one having a different type of header. One connection form is the user-network interface (UNI), which is used between the user installation and the first ATM exchange and also within the user""s own network. The other form of connection is the network-node interface (NNI) which is used between the ATM exchanges in the trunk network. The header format for the UNI consists of the following field:
Generic flow control (GFC) field of 4 bits. It can provide flow control information towards the network from an ATM endpoint.
Routing field of 24 bits. Eight of the bits are VPI (virtual path identifiers) and 16 bits are VCI (virtual channel identifier). Empty cells with both the VCI and VPI set to zero indicates that the cell is unassigned.
Payload type (PT) field of 3 bits. This field is used to provide information on whether the cell payload contains user information or network information. This field is used by the network to intercept any important network information.
Cell loss priority (CLP) field containing 1 bit. This field may be set by the user or service provider to indicate lower priority cells. If the bit is set to 1 the cell is at a risk of being discarded by the network during busy times.
Header error control (HEC) field of 8 bits. This field is processed by the physical layer to detect errors in the header. The code used for this field is capable of either single-bit error-correction or multiple-bit error-detection.
As seen in FIGS. 1A and 1B, the header format for the NNI is the same as the header information of the UNI except that there is no GFC, and the VPI of the routing field is 12 bits instead of 8 bits.
Error detection occurs only within the header message. No error detection of the data occurs within the information portion of the cell. The receiving endpoint determines whether the data can be corrected or whether it must be discarded. When a link or node becomes busy, an ATM network must discard cells until the problem is resolved. The first cells to be discarded are the cells that have a CLP bit in the header set to a xe2x80x9c1xe2x80x9d. Since connection endpoints are not notified when a cell is discarded, higher layers of protocols are needed to detect and recover from errors.
A cell is sent along a channel called a Virtual Channel Connection (VCC). A VCC consists of a series of links that establish a unidirectional connection through the network that allows the flow of information from one endpoint to another endpoint. Cells on a VCC always follow the same path through the network. Therefore, each cell arrives at its destination in the same order in which it was transmitted. VCCs can be unidirectional or may occur in pairs, thus making the connection bi-directional. VCCs can be within a Virtual Path Connection (VPC), meaning a group of virtual channels that are associated together, so as to be sent as a large trunk for a part of network. The VCCs are multiplexed and demultiplexed at appropriate network nodes in the network. Each VCC and VPC have specially assigned numbers called Virtual Channel Identifiers (VCI) and Virtual Path Identifiers (VPI), respectively. These numbers help the system determine the direction in which the cells belonging to the connection should be sent and which applications should be associated with the connection.
Although cell- or packet-based transmission, switching, and network technology has been employed in broadband integrated services digital networks (B-ISDN) which rely on fiber optics, there are numerous difficulties associated with implementing such cell- or packet-based technology in a wireless communication network. These difficulties include the fact that cell- or packet-based networks and switches rely on a number of high-speed interfaces. These high-speed standard interfaces include OC-3 (155 Mbit/s), OC-12 (622 Mbit/s) and DS3 (45 Mbit/s). However a few cell- or-packet-based networks and switches support lower speed interfaces, such as T1 (1.544 Mbit/s) and the programmable rate RS-449 interface.
As a consequence, there are only a few interfaces which can support the comparatively low transmission rates (less than 1 Mbit/s to 8 Mbit/s) used in wireless communication. Although commercial satellite and wireless modems support these low transmission rates using an RS-449 programmable rate interface, it is difficult to implement-cell- or packet-based technology in a wireless environment using conventional interfaces because most cell or packet traffic, such as ATM, is transmitted over high rate data interfaces.
Another difficulty associated with implementing cell- or packet-based technology in a wireless communication network has to do with the fact that cell- or packet-based protocols rely on extremely low bit error ratios which are typical of fiber optics based networks. By way of example, ATM protocols assume that the transmission medium has very low Bit Error Ratios (BER) (10xe2x88x9212) and that bit errors occur randomly.
In contrast, the bit error ratios associated with wireless communication are much higher (on the order of 10xe2x88x923 to 10xe2x88x928) and tend to fluctuate in accordance with atmospheric conditions. In addition, the errors associated with wireless communication tend to occur in longer bursts. Thus, a robust error correction scheme must be employed in a wireless network in which cell- or packet-based technology is to be implemented.
In addition to the difficulties discussed above, there is another significant constraint placed on wireless communication networks which is not imposed on terrestrial based fiber optics networks. This constraint has to do with the fact that the cost of bandwidth in a wireless network is much higher than for fiber optics networks. As a consequence of having been traditionally implemented in fiber optics networks, for example, ATM based technology is not particularly efficient in its use of transmission bandwidth. Therefore, if ATM-based technology is to be implemented in wireless networks, it must achieve a more efficient use of bandwidth. One basis for such inefficiencies arises from the use of traditional signal acquisition and synchronization techniques.
Transmission links need a technique for formatting frames such that a receiver of a bit stream can recognize the boundaries where frames begin in the bit stream. Most systems accomplish this by inserting some additional bits in the bit stream which are dedicated to this purpose. Specialized hardware is used at the receiver to search for this pattern in the bit stream. It takes several samplings of the bit stream before frame boundaries are reliably recognized. These techniques lead to a loss of bandwidth, expensive hardware and a long time to achieve synchronization, especially over low speed links.
For example, there are various traditional methods used for frame synchronization in ATM, synchronous circuit systems and packet transfer systems. Many non-cell and non-packet systems, use special synchronization bits in the bit stream to achieve synchronization. ATM uses a self-delineation scheme, whereby the error detection capability of the ATM cell header checksum is used as an indication of cell synchronization. All methods generally require dedicated hardware implementations to search for the synchronization pattern and to retain synchronization. Most systems require sampling of several frames to achieve acquisition, which is of not much concern in high speed links, but is detrimental in low speed links.
Other primary access interfaces include ISDN/SS#7 (for switched digital circuits, voice, fax and video conferencing), Internet and xe2x80x9cframe relayxe2x80x9d (for LAN interconnection and Internet access) using TCP/IP or other LAN protocols. Considerations similar to those for ATM are relevant to the transmission of traffic using these other interfaces, as exemplified by the transmission of frame/relay traffic over satellite/wireless networks, although some differences are known in the art. For example, unlike ATM cells, frame relay packets are variable lengths. Thus, the frame formats used to communicate between the satellite/wireless terminals are arranged to transport variable length packets efficiently.
As explained in the U.S. Provisional Application S. No. 60-052,359, which is incorporated herein by reference, the frame/relay uses a robust, flexible frame format between two communicating terminals which allows the transport of several variable sized Spackets (segmented packets) in a frame and also allows a single Spacket to be carried over several frames, whichever the case might be. Also, the frame format allows fast synchronization and the exchange of coding information. Each frame contains Reed-Solomon (RS) check bytes that are used for error correction and to enhance the quality of the satellite/wireless link. The number of RS check bytes in a frame can be changed on the fly, without any loss of data, to compensate for varying link conditions. The decision to change the RS check bytes in a frame is based on the constant monitoring of the link quality. Several frames are also interleaved before transmission over the satellite/wireless link, to help spread the effect of burst errors over several frames, all of which can then be corrected by the FEC in the frames.
Also, Virtual Channels (VCs) can be configured to be enabled for data. compression, which means that the Spackets belonging to the VC are passed through a data compressor/decompressor combination to save bandwidth VCs can also be configured to be either high or low priority VCs and the scheduler then, uses this information to fairly transmit the various Spackets over the satellite/wireless link. To minimize the large delays introduced by the transmission of low priority packets on a low bit rate link, and the delay experienced by high priority packets which are waiting to be scheduled, the Spacket allows the segmentation of large packets into several, smaller Spackets. The delays experienced by high priority packets are substantially reduced. This also allows for efficient implementation of the compression and decompression modules.
The frame relay arrangement using Spackets also faces the problem of efficiently using bandwidth in a wireless network. Therefore, if frame relay (Spacket)-based technology is to be implemented in wireless networks, it must achieve a more efficient use of bandwidth. These same goals apply to ISDN/SS#7 transmissions, Internet transmissions and those generally using TCP/IP protocols. However, no solution to problems blocking achievement of these goals is seen in the prior art.
U.S. Pat. No. 5,568,482 relates to a low speed radio link system and method designed for ATM transport. The system is based on a data protocol that is compatible with non-wireless ATM based data transmission systems. The data protocol incorporates a frame format that allows for the transmission of ATM cells in low speed, high noise links. However, the data protocol is rigid and does not account for partial or compressed cells. Similarly, this prior art scheme fails to accommodate flexible data-payloads or flexible block codes for error correction. The problems of conventional ATM-synchronization in a low speed noisy environment are avoided by establishing a data frame with 45 ATM cells in its payload and by using a 7-byte header and individual 1-byte subframe headers, with each subframe having 5 53-byte ATM cells. The 2400 byte frame is sized to have an integer relationship with the standard 8 kHz sync clocks, and the framing header serves to indicate the start of a frame. The frame header can also have one byte to represent standard BIP-8 for the previously sent frame. The 1-byte subframe header can also provide a periodically repeating framing information that can serve synchronization. Because the framing structure is at predictable ATM cell locations, and are repeated continuously there, rapid re-synchronization can be achieved. Moreover, the internal ATM cell checksum present in the standard ATM cell can verify error free transmission.
A further prior art technique for synchronization in a wireless ATM network is called the Limitless ATM Network (LANET) protocol. The LANET protocol is combined with the Reed-Solomon forward error correction scheme and simple error tolerant addressing (multiple redundancy addressing). The LANET provides a framing structure around ATM cells for transmission purposes and provides a regular frame Mbit pattern for cell extraction. A 15 byte overhead, which includes LANET frame and subframe headers, are used in conjunction with traditional cell header error detection methods (HEC) to enhance cell delineation in noisy environments. Rather than using block error correction schemes to protect the header, LANET uses error-tolerant addressing schemes (multiple redundancy addressing) so that multiple virtual circuits to the same destination are established. The LANET protocol is touted to have the ability to sort quickly through the bits to locate headers that obey a certain periodicity constraint because they are simple, predictable and have reasonable chance of surviving noise.
However, the present invention and the prior art differ in both the framing and content of the transmission, and thus would differ in the algorithms applied for synchronization and acquisition. First, the framing composition in the present invention does not utilize a single frame header for a group of frames, but uses a header for each frame and appends RS checking onto each frame. This differs from the subframes used in the prior art, which rely on only a single bit of overhead per subframe but require a shared header of 7 bytes. Although the prior art does teach reliance on both error correction decoding and use of other frame header information every frame to maintain frame synchronization, there is no teaching of the algorithm used and, even on the basis of the limited disclosure, there would be a difference from that proposed in the present disclosure.
The present invention overcomes the above-mentioned problems associated with implementing cell or packet-based technology in a wireless communication network by providing a frame format for a communication signal containing a bit stream, such as one including asynchronous transfer mode (ATM) formatted data.
The present invention also overcomes the above-mentioned problems associated with implementing frame relay-based technology in a wireless communication network, carrying frame relay formatted data supported by TCP/IP and other LAN protocols, by providing a frame format for a communication signal containing a bit stream including Spacket formatted data.
The present invention also overcomes the above-mentioned problems associated with implementing ISDN/SS#7-fornatted data in a wireless communication network, by providing a frame format for a communication signal containing a bit stream including appropriately formatted data.
In the ATM environment, the invention concerns a portion of the ATM Link. Accelerator (ALA), which is located between the ATM switch and the WAN transmission device. The ALA design is based upon an architecture and frame structure which encompasses adaptive rate interfaces, Reed-Solomon coding and decoding, interleaving and deinterleaving, and frame assemble/disassemble functions. Improvements are also made in adaptive coding, frame synchronization, head compression and data compression.
A particular problem which the present invention overcomes is the inefficient use of available bandwidth. For example, ATM technology uses small size cells (53 octets), each having 5 octets that are used as a header to provide a header-error-correcting checksum and virtual path (VP) and virtual circuit (VC) ID numbers and control. The cells are assembled into frames for transmission and, using conventional synchronization techniques, would require the commitment of additional overhead bits.
Accordingly, an object of the present invention is to provided an algorithm, applicable to several cell- and packet-based protocols, that is simple and streamlined and can be implemented efficiently in software, such that specialized hardware for bit and frame synchronization pattern search is not required.
Another object is to provide an algorithm that is adaptive and loss-less, and is totally transparent to any network switches, including those specifically directed to ATM, frame relay, ISDN or SS#7 transmissions.
A further object of the present invention is to use a synchronization and acquisition algorithm that does not require any a priori knowledge of the configuration of Virtual Circuit Identifiers in use over the link, or otherwise impose any constraints on the range of Virtual Circuit Identifiers (VCIDs) or Virtual Path Identifiers (VPIDs), such as those used by the ATM switches or frame relay-type switches.
Yet another object of the present invention is to achieve bit and frame synchronization between the transmitter and the receiver over a transmission link without use of any special dedicated synchronization patterns within the data stream to perform frame acquisition and synchronization functions, without use of any bandwidth overhead and without use of any specialized hardware.
The present invention takes advantage of the fact that the transmission link, which carries cell (e.g., ATM) and packet (e.g., Spacket) traffic, has varying amounts of idle cells or packets during start-up as well as during operations.
The present invention uses the bits in the idle cells or packets to generate synchronization patterns which can be recognized by the receive software to determine frame boundaries rapidly and with a high degree of reliability.
The present invention determines frame boundaries rapidly, with just one sampling of 2I frames, where I is the interleaver depth.
Finally, the present invention provides an acquisition and synchronization technique that is very robust, such that the probability of error in synchronization is extremely small, even at very high BERs, and, if an error is made, the error can be detected within a second attempt at synchronization.
In accomplishing these objects, the present invention uses a scheme for achieving rapid bit, byte and frame synchronization between the transmitter and the receiver, without using a dedicated synchronization pattern and without randomly searching for the frame boundary. During acquisition, the transmitter fills the entire payload of the frame with a pattern that is used by the receiver to determine the location of the frame boundary. This procedure is deterministic and in most cases, a single sampling of 2I frames allows the receiver to adjust the frame boundary to the correct value.
As to synchronization, the unique content of the cell or packet framing and a novel algorithm that takes advantage of the fact that the satellite/wireless link carries varying amounts of idle cells during startup and normal operation. The algorithm uses these idle bits to generate synchronization patterns which can be recognized-rapidly and with high reliability in determination of frame boundaries. This procedure requires no overhead bits in the data stream, which results in a small savings in bandwidth.
Specifically, with respect to an ATM transmission system, the ALA transmit bit stream consist of a sequential train of interleaved frames, forming an xe2x80x9cinterleaver framexe2x80x9d of fixed size that is n octets long and has I frames. Each frame includes a frame header (2 octets), payload (fixed cells and variable packets) and error correcting check bits (2t octets), and the size of the packets and check bits can vary inversely to maintain a fixed frame size. The frame header includes a frame number that is incremented modulo 8 and assigned to each frame. Also included are count, size and coding information.
The invention uses (1) the frame sequence number field in the header of every frame and (2) the Reed-Solomon decoding result as a method to verify and maintain frame synchronization. Specifically, if proper frame synchronization has been achieved at the receiver, all (most) frames should have the correct incrementing frame sequence number and the Read-Solomon decoder should declare success in correcting all (most) frames. Thus, once synchronization has been achieved, received frames are monitored for correctness (absence of Reed-Solomon decoder errors and matching frame-number and correct header fields).
These and similar considerations apply to the use of the present invention in a to frame relay, ISDN or SS#7-type system, where fast and efficient acquisition and synchronization is desired.
As used herein, the term xe2x80x9ccellxe2x80x9d shall be used to mean a fixed size container, such as the ATM cell, and the term xe2x80x9cpacketxe2x80x9d shall be used to mean and a variable size container, and the term xe2x80x9ccell/packetxe2x80x9d shall mean generically either or both such container arrangements.